COMMENT ⊗   VALID 00008 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.DEVICE XGP
C00003 00003	.SELECT 3
C00005 00004	.sec(Memory structure)
C00010 00005	.sec(Known Page Table)
C00012 00006	.sec(Registers)
C00014 00007	.sec(Instructions)
C00017 00008	.sec(Map Manipulation)
C00021 ENDMK
C⊗;
.DEVICE XGP
.FONT 1 "NGR25";
.FONT 2 "FIX25";
.FONT 3 "CLAR30";
.macro chart ⊂
.BEGIN GROUP NOFILL SELECT 2;
.⊃
.macro endchart ⊂
.END
.⊃
.macro sec(name) ⊂
.BEGIN SELECT 3;
.if lines<8 then skip to column 1 else skip 2;
.nofill;
name
.END; FILL; ONCE PREFACE 0;
.⊃
.AFTER PAGE ⊂
.EVERY HEADING(A Recursive Paged Virtual Memory,,{PAGE});
.AFTER PAGE ⊂⊃;
.⊃
.SELECT 3;
.center
.skip 10
A Recursive Paged Virtual Memory
.SELECT 1;
Larry Masinter

11/2/74
.skip 10
.sec(Abstract)
This virtual memory scheme is an attempt to provide a virtually
unlimited address space while allowing programs to use relatively
short addresses for local references. A basic address mapping
scheme for variable length addresses is described.
.sec(Disclaimer)
The ideas presented herein are acknowledged to be half-baked. Further,
this does not begin to satisfy the specification of the assignment.
However, I think it is an interesting idea.
.sec(Hardware)
The scheme is described in terms of interpreting instructions and addresses
on an unspecified 16 bit machine with up to 64K (2↑16) words of main memory.
Details for a particular machine have not been worked out.
.sec(Memory structure)
The memory is structured as a 256-ary tree; each of the nodes
is a page table, and each of the leaves is a page of data or
instructions. A virtual address is completely specified by a sequence
of indices from the root node. The first byte gives the index
in the root page table. 
This entry contains an indication that it is either a pointer to a data page
or to another page table. If it points to a data page, the next byte
determines the word number within that data page; if a page table, the
process is iterated.
Looking from the bottom up, each page (either data or page table, except
for the root)
has a PARENT page table, and a page number (within its parent).
Alternatively, a page table entry may contain an indication
that the page is not in core, and the high order bits of its
disk address. The low order bits are determined by the page number.

Additionally, each page in the virtual memory has a unique disk address.
As the physical size of the disk is ?, this limits the virtual
memory size to be that of the disk. The disk addresses of those
pages which are currently in core is maintained in a separate table,
the Known Page Table.
.sec(Data Structures)
Each page is either a data page containing 256 words (512 8-bit bytes)
of instructions or data, or else a page table, containing 256
page table entries (PTE's). The format of a PTE is:

.chart

bit: 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 
    +---------------+---------------+
    |0| high order bits disk address|  page not in core
    +---------------+---------------+



bit: 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 
    +---------------+---------------+
    |1|1| reserved  | RMP           |   data page
    +---------------+---------------+



bit: 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 
    +---------------+---------------+
    |1|0| reserved  | RMP           |    pointer to page table
    +---------------+---------------+


notes:
(1) a few disk addresses are reserved for special meaning; e.g.
  zeros:	pseudo data page of all zeros.
  extend:	this turns in to a page table, each entry of
		which is a "zeros" entry except the first, which
		contains an "extend". Good for stacks.

(2) RMP: Real Memory Page. A page number in real memory (0-255).

(3) bit 0 is the "in core" bit. A reference thru an entry with
    this bit off will fault.

(4) If in core, bit 1 is the "data page" bit; if on, the RMP pointed
    to contains data; otherwise it contains a page table.

(5) The low order bit of the disk address is determined by
    the low order bit of the page number in its parent.

(6) Bits 2-7 will contain protection information
.endchart
.sec(Known Page Table)
The main other data structure used in the memory scheme is a (fixed)
two page array called the Known Page Table. It contains additional
information about those pages which are in core. The first part of
the KPT contains the real disk address of the page. The second part
of the KPT contains the parent information. PARENT(rmp) is either:
.chart
bit: 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 
    +---------------+---------------+
    |0| high order bits disk addr.  |   parent not in core
    +---------------+---------------+
.endchart
.chart
bit: 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 
    +---------------+---------------+
    |1| pn          | RMP           |   parent in core; RMP
    +---------------+---------------+   is its real address;
					pn is high order bits of
					page number within parent.
.endchart
.sec(Registers)
As the depth of the virtual memory tree increases,
addresses relative to the root of the tree grow longer.
Thus, 4 address "registers" are provided. Memory references are
always made with respect to one of these registers. Each register
contains an 8-bit real memory page number. The four pages referred
to in the registers are all page tables; and all are considered
locked into core until the values of the registers change.

.chart
	SP0:	stack
	PC0:	program counter
	DP0:    data
	GP0:	general register
.endchart
Each opcode specifies one of these address registers
as a context in which the following bytes are interpreted.
SP and PC each have two byte extensions:
SP1 and PC1 are the real memory pages (RMPs) of the current stack
and program counter, SP2 and PC2 are offsets therein. PCX is a one-bit
odd byte indicator. Thus, for example,
the 16 bit quantity <SP1,SP2> is the real memory address (RMA) of
the top of the stack. Stored in the memory are the virtual addresses
of DP0, PC1, and SP1 with respect to the root.
.sec(Instructions)
An instruction consists of a 1 byte opcode, followed by an arbitrary
number of bytes of address. Each instruction has addressing mode(s).
An addressing mode is either relative to a particular register, or
a mode local to SP or PC. Various instructions are presented below:
.chart

 Instruction	Mode	Interpretation


	  Standard Instructions

  JUMP b1...bn  PC0	Fetch [PC0; b1,...,bn] as next opcode;
			reset PC0 to RMP of last page table found,
			PC1 to last page, and PC2 to bn; set PCX
			to 0. (note that n ≥ 2). Might also provide
			a JUMP relative to ROOT.

  LJUMP b	PC	Reset PC2 to b; set PCX to 0.
			(note that one cannot jump to an odd byte)
  
  PUSH b1...bn  SP,DP0  Fetch [DP0; b1, b2, ... , bn]; store at
			RMA <SP1,SP2>; decrement SP (see below).

  POP b1...bn	SP,DP0	Increment SP (see below) and store the
			contents of <SP1,SP2> at [DP0; b1,...,bn]

  STKNTH n	SP	Push SP+n onto stack. (note that stacks
			grow from large addresses to small; this
			is so that indirect addressing off the stack
			can work)

  ADD, SUB, etc	SP   single byte instructions which work on the top
		     of the stack.
.endchart
.chart

	Register manipulations

 SETSP b1...bn  DP0,SP  Reset SP (works like JUMP).

 UPDP		DP      Set DP0 to its parent.

 DOWNDP n	        Set DP0 to its n'th entry. 
.endchart
.sec(Map Manipulation)
Instructions are provided to manipulate the address space: 
the main operation would be to reset page n in DP0 to contain
(zeros, extend, empty, a copy of some other page). Alternatively,
provisions for moving one PTE to another location are provided.
.sec(Incrementing and Decrementing)
When the virtual address space is not linear, the conventional concept
of "next word" requires some redefintion when at page boundaries.
If at the last word of a page, the next word can be defined by:
.chart; fill;
go up until you are not at the last entry of a PT; increment the
page number, and then go down the 0 entries until you hit a data page.
.endchart
A similar mechanism can be defined for decrementing a register.
.sec(More Problems and a Few Solutions)
A page table, when on disk, contains disk address PTE's only. When
it is brought into core, the Known Page Table is searched for entries
containing its daughters; if they are found, the map is updated
to show that these pages are in core. This mechanism is necessary
if one is to allow non-connected subparts of the tree to be in core.

Arbitrary address arithmetic is hard, since addresses are not
uniform in length. The main facilities available are indirection off
the stack. I gave some thought to problems of variable length
arithmetic but didn't pursue it.

Unfortunately, the tree must actually be a tree and not an arbitrary
graph; each page must have a unique owner.

When a page is swapped out, the entries in its parent (if in core),
and its immediate descendants (again if in core) need to be marked.
.sec(Criticisms)
The major issues of virtual memory on single user machines have not
been addressed. The most important factor distinguishing the situation
from multiprocessing situations is that, there are no other users
waiting to run if a single user blocks. This weighs heavily against
demand page replacement strategies. Using the principle that programs
tend to use locallized addressing, some principle of fetching the
neighbors of a data-page when it is fetched is not unreasonable.
Constraints can also be placed on which pages can be thrown out.
In particular, all incore pages should have some path to one of the
PT's pointed to by the registers (as those are the only way of getting
at a page in core).